package 二叉树;

/**
 * https://leetcode-cn.com/problems/increasing-order-search-tree/
 * 1、创建一颗新树用于返回；2、递归向左找到最小加在新树中；3、断开老树的左连接防止下一个递归中无限循环
 */
public class 递增顺序搜索树 {
    TreeNode cur = new TreeNode();
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyHead = new TreeNode();
        cur = dummyHead;
        fun(root);
        return dummyHead.right;
    }
    public void fun(TreeNode root){
        if (root == null){
            return;
        }
        fun(root.left);
        cur.right = root;
        root.left = null;
        cur = root;
        fun(root.right);
    }
}
